// 使用中心扩散法
export function longestPalindrome(s: string): string {
    let maxLen = 1;
    let maxIndex = 0;
    for (let i = 0; i < s.length; i++) {

        const len1 = expandAroundCenter(i, i, s);
        const len2 = expandAroundCenter(i, i+1, s);
        const len = Math.max(len1, len2);
        if (len > maxLen) {
            maxLen = len;
            maxIndex = i;
        }
    }

    return getSubStr(maxIndex, maxLen, s);
};

function getSubStr (centerIndex: number, len: number, s: string) {
    const left = centerIndex - ((len-1)>>1);        // 除2并向下取整，使用 >>1，适用于非负数
    const right = centerIndex + (len>>1);
    return s.substring(left, right+1);
}

function expandAroundCenter (left: number, right: number, s: string): number {
    while (left >= 0 && right <= s.length && s[left] === s[right]) {
        left--;
        right++;
    }
    // 出了 while 循环，说明此时 left right 都不满足要求
    // 满足要求的 left = left + 1
    // 满足要求的 right = right - 1
    return (right-1) - (left+1) + 1;
}